package com.peng.leetcode.tree;

import java.util.Deque;
import java.util.LinkedList;

/**
 * BSTIterator
 *
 * 173. 二叉搜索树迭代器
 *
 * @author: lupeng6
 * @create: 2021/1/28 15:11
 */
public class BSTIterator1 {

    public static void main(String[] args) {

    }

    private Deque<TreeNode> stack = new LinkedList<>();

    public BSTIterator1(TreeNode root) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
    }

    public int next() {
        TreeNode node = stack.pop();
        if (node.right != null) {
            stack.push(node.right);
            TreeNode top = stack.peekFirst();
            while (top.left != null) {
                stack.push(top.left);
                top = top.left;
            }
        }
        return node.val;
    }

    public boolean hasNext() {
        return !stack.isEmpty();
    }
}
